package com.ljy.my_study.lintcode.子集;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/** 
* @author James
* @date 2018年9月25日 
*/
public class TestMain {
//	描述
//	给定一个含不同整数的集合，返回其所有的子集
//
//	子集中的元素排列必须是非降序的，解集必须不包含重复的子集
//
//	您在真实的面试中是否遇到过这个题？  
//	样例
//	如果 S = [1,2,3]，有如下的解：
//
//	[
//	  [3],
//	  [1],
//	  [2],
//	  [1,2,3],
//	  [1,3],
//	  [2,3],
//	  [1,2],
//	  []
//	]
//	挑战
//	你可以同时用递归与非递归的方式解决么？
	public static void main(String[] args) {
		TestMain testMain=new TestMain();
		int[] nums= {1,1,0};
		List<List<Integer>> listList=testMain.subsets(nums);
		System.out.println(listList);
		System.out.println(listList.get(2).equals(listList.get(4)));
	}
	
	public List<List<Integer>> subsets(int[] nums) {
		Arrays.sort(nums);
		List<List<Integer>> listList=new ArrayList<>();
		Set<List<Integer>> listSet=new HashSet<>();
		listList.add(new ArrayList<>());
		int len=nums.length;
		int count=0;
		List<Integer> newl=null;
		while(count<len) {
			int size=listList.size();
			for(int i=0;i<size;i++) {
				newl=new ArrayList<>(listList.get(i));
				newl.add(nums[count]);
				if(listSet.contains(newl)) {
					continue;
				}
				listList.add(newl);
				listSet.add(newl);
			}
			count++;
		}
		return listList;
	}	
	
	public List<List<Integer>> subsets2(int[] nums) {
		List<List<Integer>> listList=new ArrayList<>();
		listList.add(new ArrayList<>());
		int len=nums.length;
		int count=0;
		
		
		
		return listList;
	}	
}
